﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0087_CanJump : IAlgorithm
    {
        // 55. 跳跃游戏

        // 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
        // 数组中的每个元素代表你在该位置可以跳跃的最大长度。
        // 判断你是否能够到达最后一个下标。

        // 提示：
        //  1 <= nums.length <= 3 * 10^4
        //  0 <= nums[i] <= 10^5
        public void Test()
        {
            // 算法参数定义
            //var nums = new int[] { 2, 3, 1, 1, 4 };
            var nums = new int[] { 3, 2, 1, 0, 4 };
            //var nums = new int[] { 0, 4 };
            //var nums = new int[] { 1, 4 };
            // 算法执行与打印
            Console.WriteLine(CanJump(nums));
        }

        // 算法
        public bool CanJump(int[] nums)
        {
            int lastIndex = 0, curIndex = 0;
            while (lastIndex + nums[lastIndex] >= curIndex && curIndex < nums.Length - 1)
            {
                if (curIndex + nums[curIndex] > lastIndex + nums[lastIndex])
                    lastIndex = curIndex;
                curIndex++;
            }
            return lastIndex + nums[lastIndex] >= nums.Length - 1;
        }
    }
}
